
"""
283. Move Zeroes

https://leetcode.cn/problems/move-zeroes/
"""

from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        size = len(nums)
        if size <= 1:
            return
        # i = 0
        # while i < size:
        #     if nums[i] == 0:
        #         for j in range(i+1, len(nums)):
        #             if nums[j] != 0:
        #                 nums[j], nums[i] = nums[i], nums[j]
        #                 i+= 1
        #         i+=1
        #     else:
        #         i += 1

        # 重点是想清楚“循环不变量”的含义
        k = 0  # nums中，[0,k)的元素均为非0元素
        for i in range(len(nums)):
            if nums[i] != 0:
                if k != i:
                    nums[k], nums[i] = nums[i], nums[k]
                    k += 1
                else:
                    k += 1


def test():
    obj = Solution()
    nums = [0, 1, 0, 3, 12]
    obj.moveZeroes(nums)
    print(nums)


if __name__ == "__main__":
    test()
